#include <iostream>
#include <cassert>

using namespace std;

// 将元素少的根节点指向元素多的根节点, 记录元素个数
namespace UF3{
	class UnionFind{
		private:
			int *parent;
			// sz[i]表示以i为根的集合中元素个数
			int* sz;
			int count;
		public:
			UnionFind(int count){
				parent = new int[count];
				sz = new int[count];		// 开辟空间
				this->count = count;
				for(int i = 0; i < count; ++i){
					parent[i] = i;
					sz[i] = 1;				// 初始每个集合只有一个元素
				}
			}

			~UnionFind(){
				delete[] parent;
				delete[] sz;
			}

			int find(int p){
				assert(p >= 0 && p < count);
				while(p != parent[p]){
					p = parent[p];
				}
				return p;
			}

			bool isConnected(int p, int q){
				return find(p) == find(q);
			}

			void unionElements(int p, int q){
			
				int pRoot = find(p);
				int qRoot = find(q);

				if(pRoot == qRoot){
					return;
				}
				
				if(sz[pRoot] < sz[qRoot]){
					parent[pRoot] = qRoot;
					sz[qRoot] += sz[pRoot];	// 集合元素数增加
				}else{
					parent[qRoot] = pRoot;
					sz[pRoot] += sz[qRoot];
				}
			}
	};
}
